import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

/**
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode
 * left; TreeNode right; TreeNode(int x) { val = x; } }
 */

/*
 * 特性A，对于前序遍历，第一个肯定是根节点； 特性B，对于后序遍历，最后一个肯定是根节点；
 * 特性C，利用前序或后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左子树和右子树；
 * 特性D，对左子树和右子树分别做前面3点的分析和拆分，相当于做递归，我们就可以重建出完整的二叉树；
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || preorder.length == 0){
            return null;
        }

        // 定义根节点
        TreeNode root = new TreeNode(preorder[0]);
        
        // 左右子树 中序遍历
        Vector<Integer> leftInorder = new Vector<>();
        Vector<Integer> rightInorder = new Vector<>();

        // 左右子树 前序遍历
        Vector<Integer> leftPreorder = new Vector<>();
        Vector<Integer> rightPreorder = new Vector<>();


        // 划分左右子树, 获得左右子树的中序遍历序列
        for(int i=0; i <= inorder.length - 1; i++){
            leftInorder.add(inorder[i])
            if(inorder[i] == root.val){

            }
        }

        // 左右子树  获得  前序遍历和中序遍历  递归
        root.left = "";
        root.right = "";
        return root;
    }

    // 从前序遍历preorder中拿到根节点
    // 结合根节点，从中序遍历inorder中拿到左右子树的中序遍历
    // 根左右
    // 左根右
    // 左右根

    private TreeNode getChildNode(TreeNode root) {

        // 连接左结点
        root.left = "";

        // 连接右结点
        root.right = "";

        return root;

    }

}